import java.util.Arrays;

public class Solution1262 {
    public int maxSumDivThree(int[] nums) {
        int[] f=new int[3];
        boolean[] b=new boolean[3];
        b[0]=true;
        for (int num : nums) {
            boolean[] nb= Arrays.copyOf(b,3);
            int[] g=Arrays.copyOf(f,3);
            for (int i = 0; i < 3; i++) {
                if (b[i]){
                    g[(i+num)%3]=Math.max(g[(i+num)%3],f[i]+num);
                    nb[(i+num)%3]=true;
                }
            }
            b=nb;
            f=g;
        }
        return f[0];
    }

    public static void main(String[] args) {
        System.out.println(new Solution1262().maxSumDivThree(new int[]{3,6,5,1,8}));
    }
}
